/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._17_12;

import lombok.val;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._17_12
 * @ClassName: ConvertBiNode
 * @Author: linyaonan
 * @Date: 2020/4/3 11:08
 */
public class ConvertBiNode {

    public TreeNode convertBiNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode pre = new TreeNode(-1);
        bfs(root, pre);
        return pre.right;
    }

    private TreeNode bfs(TreeNode node, TreeNode pre) {
        if (node != null) {
            // 左遍历
            pre = bfs(node.left, pre);
            // 断链
            node.left = null;
            // 前驱节点与当前节点位置交换
            pre.right = node;
            // 遍历后移
            pre = node;
            // 右遍历
            pre = bfs(node.right, pre);
        }
        return pre;
    }

}
